Journal d'un Terrien
Web log de Serge Boisse
On line depuis 1992 !
http://sboisse.free.fr/science/maths/Mes Recherches mathematiques/creneaux et briques.php
Créneaux et Briques : l'art de compresser des séquences de chiffres binaires
Auteur : Serge Boisse
Date : Le 15/09/2022 à 09:09
L'idée est de représenter des séquences binaires cycliques, c'est à dire qui se répètent indéfiniment. Cela donne lieu à de nouveaux (?) objets et espaces mathématiques
Cette page est une recherche en cours (2025), elle est loin d'être terminée, et je pense la compléter et/ou la modifier de temps en temps
Mais si vous avez des idées, laissez-les en commentaire !
Voir aussi: répétitions dans une séquence et SAT
Créneau
Les créneaux représentent la description minimale d'une suite infinie périodique de bits. Ainsi le créneau
Voici une image du créneau
A tout créneau
Définition
On appellera créneau une chaine constituée des symboles 0 et 1,terminée par ".." (attention uniquement deux points et pas trois) et respectant les règles suivantes :
- si
En conséquence
Par exemple
Attention, la concaténation de deux créneaux différents n'est pas forcément un créneau !
Par exemple "101.." concaténé à "010" donnerait "101010..." qui n'est pas un créneau puisque simplifiable en "01.."
La Fortification
La longueur L(C) d'un créneau C est le nombre de symboles 0 ou 1 qu'il contient. Etant donné que les créneaux représentent en fait des répétitions, j'utiliserai parfois le mot période à la place.
Dans le processus de construction par concaténation, si la longueur de la chaine AB, c'est à dire L(A)+L(B), est un nombre premier, alors
Cette construction est elle unique ? Non ! Prenons
Les premiers créneaux sont
soit, en ignorant les zéros initiaux, les valeurs décimales
0,1,1,2,1,2,3,4,5,6,1,2,3,4,3,8,9,12,13,14 (pas dans OEIS)
Faux créneaux
Les suites de symboles listés ci-dessous ne sont pas des créneaux car ils peuvent être simplifiés :
Dans ce qui suit le "+" en exposant signifie "répéter le symbole au moins deux fois, mais pas un nombre infini de fois")
Les fractions sont obtenues en préfixant le créneau par "0." et en cherchant la fraction correspondante au nombre binaire obtenu.
bref, aucune suite des symbole {0|1} constituée d'une répétition ne donne un créneau.
Créneaux et fractions
Comme on peut préfixer un créneau par "0.", on peut les mettre en relation avec certains réels compris dans l'intervalle [0,1]. Ces réels ont une expansion infinie qui se répète, ce sont donc des nombres rationnels positifs. Donc à chaque créneau correspond une fraction irreducible. Par exemple le créneau
Donc les premiers créneaux ci-dessus correspondent aux fractions
0,1,
1/3, 2/3,
1/7, 2/7, 3/7, 4/7, 5/7, 6/7
1/15, 2/15, 1/5, 4/15, 2/5, 7/15, 8/15, 3/5, 11/15, 4/5, 13/15, 14/15
1/31...
Mais attention, toute les fractions ne donnent pas un créneau !
En effet par exemple la fraction
En revanche le nombre binaire
Quelles fractions donnent des créneaux ? Les fractions p/q, q>2, 1<p<q, ont une expansion binaire périodique qui commence juste après le "." si et seulement si p n'est pas pas multiple de 2, et donc correspondent à des créneaux. cf Periodic decimal fractions (page web)
par exemple 1/9 = 7/63 correspond au créneau
La longueur du créneau correspondant à 1/p (p premier impair) est un diviseur de p-1 ; si la période est p-1, alors p est premier mais l'inverse n'est pas toujours vrai : 1/7->001..
Si p est premier impair et si la période de 1/p est p-1, alors, les fractions x/p, 1<x<p, ont une période qui a la même longueur et contient les mêmes bits, permutés cycliquement.
Si p est premier impair, alors s est le plus petit entier tel que
Si la longueur de la période de 1/p est
Applications interactives
nombre décimal ou fraction->binaire
L'aplication ci dessous convertit un nombre réel positif ou une fraction en chaîne binaire. Essayez "3.14" ou "1/3"
Fraction vers créneau (ou pas)
On peut le vérifier avec ce calculateur de la période binaire d'une fraction , qui donne donc le créneau éventuellement associé à la fraction ; ainsi 1/6 -> 0.0(01) ne donne pas un créneau...
Ce sera un créneau si et seulement si la partie fixe est "0."
adapté de # Find Recurring Sequence in a Fraction (page web)
Créneau vers fraction
Ce programme st incroyablement rapide.
compresseur de suite de symboles
Essayons le code de compression des répétitions
Entrer une séquence de symboles à compresser, comme 001001 ou abbabb
Attention, pas de parenthèses ni de ":" dans les symboles !
Fraction la plus proche d'un réel décimal
calcul de fractions continues
Fraction la plus proche d'un réel binaire
La même chose en acceptant une entrée en binaire fractionnaire :
période d'une fraction décimale
Calcul de la période (décimale ) d'une fraction :
Ce qui permet de corroborer les résultats de la thèse PERIODIC DECIMAL FRACTIONS (page web)
Structure de
Opérations sur
Soit A et B deux crénaux. On définit les opérations suivantes :
- Unaires
- Binaires
- Extérieures
L'application ci dessous permet de tous les tester !
négation d'un créneau
La négation NOT d'un créneau (inverser tous les bits) est intéressante :
si un créneau correspond à une fraction a/b, alors en inversant bit par bit ce créneau, il correspondra à la fraction (b-a)/b :
renversement REV
Pour le renversement (gauche-droite) REV c'est moins clair :
| x | REV |
|---|---|
| 01=>1/3 | 10=>2/3 |
| 001=1/7 | 100=>4/7 |
| 010=>2/7 | 010=>2/7 =! |
| 011=> 3/7 | 110=>6/7 |
| 101=>5/7 | 101=>5/7 =! |
| 0001=>1/15 | 1000=>8/15 |
| 0010=>2/15 | 0100=>4/15 |
| 0011=>1/5 = 3/15 | 1100=>4/5 = 12/15 |
| 0110=>2/5 =6/15 | 0110=>2/5 =! |
| 0111=>7/15 | 1110=>14/15 |
| 1001=>3/5 =9/15 | 1001=>3/5 =! |
| 1011=>11/15 | 1101=>13/15 |
Notons que si on note b[n]c le changement de base de n depuis la base b vers la base c, par exemple 2[x](1/2), décalé.
Avec C => a/b,
bien sûr REV(NOT(C)) = NOT(REV(C)), L(REV(C)) = L(C), et les fractions ont même dénominateur b (avant réduction à leur valeur irréductible)
Je n'ai pas trouvé de règle simple pour le numérateur du résultat c/d :
Pour L=2 :
a 0 1 2 3
d 0 2 1 3
Pour L=3;
a 0 1 2 3 4 5 6 7
d 0 4 2 6 1 5 3 7
Pour L=4; et a de 1 à 15, on a
a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
d 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Mais la séquence est dans OEIS ! http://oeis.org/A030109
The sequence a(n) divides naturally into blocks of length 2^k, k = 0, 1, 2, ... On block k, let n go from 0 to 2^k-1, write n in binary using k bits and reverse the bits.
If 2*2^k<= n<3*2^k then a(n) = 2*a(n-2^k); if 3*2^k<= n<4*2^k then a(n) = 1+ a(n-2^k) starting with a(1) = 0
Dupliquer D
La duplication D(C) consiste à dupliquer un par un les bits du créneau C. Par exemple D(0100..) = 00110000.. donc L(D(C)) = 2L(C)
La réponse est intéressante :
si n=L(C) est la longueur (nombre de bits) de C, alors
par exemple pour C=0001 => 1/15, L(C)=4 et D(C) = 00000011 => 1/85 parce que
La suite des d(n), pour n croissant, est 1,5,21,85,341,1365,5461... qui est la suite A002450 de OEIS. Cette suite est très intéressante, entre autre parce que la suite de Conjecture de Syracuse à partir de d(n) arrive à 1 en exactement 2n+1 étapes ; ou encore parce que d(n) est la n-1 ième puissance de 5 dans le calcul "nombral" (numbral calculus) où l'on remplace l'addition par bitwise OR et la multiplication par le SHIFT-OR. cf http://oeis.org/A048888
Notons que le calcul de n à partir de a et b n'est pas trivial. cf Fraction vers créneau (ou pas)
Et le numérateur c ? Il est le a-ième terme de la suite 1,4,5,16,17,20,21,64,65,68,69... qui est la suite http://oeis.org/A000695 , ou encore celle des nombres qui en base 4 s'écrivent uniquement avec des 0 et des 1, ce qui n'est pas sans lien avec les recherches sur la multiplication binaire sans retenue (page sur mon site) : en effet
c=a@a où @ est la multiplication binaire sans retenue !
ou encore la multiplication dans le corps GF[2]
#TBC
propriétés :
D(A) OR D(B) = D(A OR B), et de même pour AND et XOR (mais pas ADD)
REV(D(A)) = D(REV(A)) et de même pour INV.
IMPAIR(D(A)) = PAIR(D(A)) = A
IMPAIR o ADD o DUP = XOR
OR
Attention, si les deux créneaux n'ont pas la même longueur, il faut les "prolonger" jusqu'à leur plus petit commun multiple
ainsi
On obtient les résultats suivants
| OR | 01=>1/3 | 10=>2/3 | 001=>1/7 | 010=>2/7 | 011(3/7) | 100(4/7) | 110(6/7) |
|---|---|---|---|---|---|---|---|
| 01 | 01=>1/3 | 11=>1/1 | 011101=>29/63 | 011111=>31/63 | 011111=>31/63 | 110101=>53/63 | 110101=>53/63 |
| 10 | 10=>2/3 | 101011=>43/63 | 111010=>58/63 | 011111=>31/63 | 101110=>46/63 | 111110=>62/63 | |
| 001 | 001=>1/7 | 011=>3/7 | 011=>3/7 | 101=>5/7 | 111=>1/1 | ||
| 010 | 010=>2/7 | 011=>3/7 | 110=>6/7 | 110=>6/7 | |||
| 011 | 011=>3/7 | 111=>1/1 | 111=>1/1 | ||||
| 100 | 100=>4/7 | 110=>6/7 | |||||
| 110 | 110=>6/7 | ||||||
| 0001 | 0101=>1/3 | 1011=>11/15 | 001101011001 |
On a donc, si A, B et C sont des créneaux, f(C) est la fraction correspondante, et L(C) la longueur du créneau : NB: je note "|" le OR, comme dans la plupart des langages de programmation :
A | B = B | A
(A | B) | C = A | (B | C)
A | A = A
L(A | B) = ppcm(L(A), L(B))
Le dénominateur de la fraction c/d associée à (A | B) est (avant réduction)
avec
Quid du numérateur ? C'est simplement le OR des deux créneaux, éventuellement répétés jusqu'à la longueur du ppcm.
ADD (+)
Attention, si les deux créneaux n'ont pas la même longueur, il faut les "prolonger" jusqu'à leur plus petit commun multiple
Il y a une petite subtilité lorsqu'on additionne deux créneaux, pour la propagation des retenues : ainsi 101.. +110.. ne donne pas 1011.. mais 1.(100)... qui n'est pas un créneau ! En effet il faut en réalité faire l'addition de suites infinies de bits :
0.101101101101101101... = 5/7
+0.110110110110110110... = 6/7
1.100100100100100100... = 11/7 qui n'est pas un créneau car >1
Ainsi l'addition des créneaux de même longueur correspond à l'addition des fractions, à ceci près que si le résultat est plus grand que 1, il n'est pas un créneau.
On a le même résultat pour des créneaux de longueur différente : on additionne les fractions.
Distance (d)
On peut considérer la distance de Hamming sur la chaine de longueur ppcm des deux crénaux, ou bien la Distance_de_Levenshtein (wikipedia) entre les deux créneaux. Les deux sont des distances au sens mathématique...
Brique
Une brique sera un créneau de période égale à une puissance de 2.
le Mur
Construction
On pourrait pense que la construction des briques est plus simple que celle des créneaux :
- si
Mais cela ne marche pas car d'après cette construction les premières briques seraient :
Or
En fait, toute chaine binaire de longueur
Si
Alors
pour
- Si
- si
Alors
Les premières briques sont donc
Les briques de longueur
Opérations
Ce sont les mêmes que pour les créneaux, plus la génération, et la coupure en 2 parties de même longueur (scission).
concaténation
La concaténation d'une brique avec elle-même n'est pas une brique. En revanche la concaténation de deux briques différentes de même longueur est bien une brique, en effet le résultat ne peut contenir de répétition.
scission
La scission d'une brique B..= XY.. donne deux briques X.. et Y.. de même longueur mais différentes, en effet si elles étaient identiques B.. serait une antibrique. X et Y sont des briques parce que ??? #TBC
Duplication
La duplication d'une brique produit une autre brique, en effet si la brique dupliquée B à une longueur n, D(B) aura une longueur 2n et ne contiendra pas de répétitions.
#TBC
Peigne (OR de trois briques)
fabriquer les créneaux par OR / Union de briques ? and ?
changement de numéro de variable SAT
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.